import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class L239 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        int[] nums = {1, 3, 1, 2, 0, 5};
//        int[] nums = {9, 10, 9, -7, -4, -8, 2, -6};
        int k = 3;
        int[] ints = new Solution().maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(ints));
    }

    static class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
//            ArrayDeque<Integer> deque = new ArrayDeque<>();
            LinkedList<Integer> deque = new LinkedList<>();
            int[] ints = new int[nums.length - k + 1];

            for (int i = 0; i < k; i++) {
                while (!deque.isEmpty() && deque.peek() < nums[i]) {
                    deque.remove();
                }
                deque.push(nums[i]);
            }
            ints[0] = deque.peekLast();

            for (int i = 1; i < nums.length - k + 1; i++) {
                if (deque.peekLast() == nums[i - 1]) {
                    deque.removeLast();
                }
                while (!deque.isEmpty() && deque.peek() < nums[i + k - 1]) {
                    deque.remove();
                }
                deque.push(nums[i + k - 1]);
                ints[i] = deque.peekLast();
            }
            return ints;
        }
    }
}
